The present invention relates to organizing and accessing data in a database and database indexes. In particular, the present invention relates to indexes and secondary index structures for indexing a table stored as primary B+tree. More particularly, the present invention relates to methods and structures for organizing and accessing databases indexed with primary B+tree structures.
In a typical relational database system, users store,.update, and retrieve information by interacting with user applications. The user applications respond to a user""s interaction by submitting commands to a database application, or server, responsible for maintaining the database. The database server responds to commands by performing the specified actions on the database. To be correctly processed, the commands must comply with the database language that the database server supports. One popular database language is known as Structured Query Language (SQL).
Various access methods may be utilized to retrieve data from a database. The access methods used to retrieve data may significantly affect the speed of the retrieval and the amount of resources consumed during the retrieval process. Many information retrieval applications make use of indices when performing content-based searches on the database data. Examples of database indices include Rxe2x88x92trees, quadtrees, and Bxe2x88x92trees.
Database indices provide organization and reference to the data in a database to permit a user to find particular items of data in the database or determine relationships among the data in the database. Database indices can also permit relationships between the data in a database and data not included in the database to be determined.
Typically, such indices are implemented using a Bxe2x88x92tree index. The index is typically built on the columns of the table, each index entry in the index having the form  less than column_value, rowid greater than , where xe2x80x9crowidxe2x80x9d uniquely identifies the row within the table that corresponds to the index entry.
Many applications involve data sets in which individual rows are identified by a primary key. The primary key uniquely identifies each row within the table and may be formed from a single column, such as social security number for an employee, or may be formed from multiple columns, such as an area code plus a seven digit local phone number. For such a table, a primary key index can be utilized.
Entries within a primary key index may have the form  less than primary key value(s), rowid greater than . A primary key index typically provides good query performance when only indexed columns are referenced in the query, in so-called index-only scans. If non-indexed columns are referenced, an index-based scan may be utilized. In an index-based scan, the primary key index structure may be traversed to obtain a rowid, which may be then utilized to access the rows within the table structure.
To avoid duplication of the primary key values as well as to speed up primary key-based retrieval efforts, a primary B+tree structure has been introduced, which may include not only the indexed column values, but also all the remaining column values of the table in the leaves of the index structure, thus rendering maintenance of a separate table unnecessary. Each row, therefore, may include both key and non-key columns. The non-key columns may be stored along with the key columns. As a result, primary B+tree structures do not incur additional input/output overhead to access the non-key columns as with a conventional table""s index-based scan.
As with a conventional heap-organized table/index pair, primary B+tree structure provides good query performance for data included in the column or columns forming the primary key. To aid in the retrieval efforts of queries based upon non-primary key columns, secondary index structures may be provided. Entries within the secondary structure may have the form  less than secondary key value, primary key value greater than .
For index-only scans, data may be extracted directly from the secondary index structure. For index-based scans, the secondary index structure may first be traversed to obtain the corresponding primary key value. The primary key value may then be utilized in a full primary key index scan of the primary B+tree structure to obtain values from other columns that are of interest.
Primary B+trees may themselves be indexed. Typically, primary key based logical row identifiers are used in secondary indexes for primary B+tree structures. However, if primary key is large, then the size of secondary index will be large leading to high storage costs, and degradation in secondary index scan performance. No known solutions exist that can address this issue.
The present invention provides a system for organizing and accessing a database. The system includes a primary B+tree index and a secondary B+tree index. A plurality of mapping table row identifiers are stored in the secondary B+tree index. A plurality of database addresses for leaf blocks of the primary B+tree index corresponding to mapping table rows are also stored in the secondary B+tree index.
Additionally, the present invention concerns a method for managing a database system. According to the method, a secondary index is created for a primary B+tree structure. The secondary index structure includes a plurality of rows each comprising an index key value, a mapping table rowid value and a guess-database block address value.
Also, the present invention provides a computer program product for performing a process of managing a database system. The computer program product includes a computer readable medium and computer program instructions recorded on the computer readable medium and executable by a processor. The computer program instructions performing the steps of creating a secondary index for a primary B+tree structure, wherein the secondary index structure includes a plurality of rows each comprising an index key value, a mapping table rowid value and a guess-database block address value.
Furthermore, the present invention provides a system for performing a database management process. The system includes a processor operable to execute computer program instructions; and a memory operable to store computer program instructions executable by the processor. The computer program instructions performing the steps of creating a secondary index for a primary B+tree structure, wherein the secondary index structure includes a plurality of rows each including an index key value, a mapping table rowid value and a guess-database block address value.
Still other objects and advantages of the present invention will become readily apparent by those skilled in the art from a review of the following detailed description. The detailed description shows and describes preferred embodiments of the present invention, simply by way of illustration of the best mode contemplated of carrying out the present invention. As will be realized, the present invention is capable of other and different embodiments and its several details are capable of modifications in various obvious respects, without departing from the invention. Accordingly, the drawings and description are illustrative in nature and not restrictive.